package com.formula.datastructure.exercise.tree;

import com.formula.datastructure.standard.queue.Queue;
import com.formula.datastructure.util.DataUtil;

/**
 * 计算叶子
 * 计算只有一个叶子的节点
 * 广度遍历
 */
public class BinaryLinkTree {
    private BinaryLinkNode root;

    /**
     * 这种方法比较方便
     *
     * @param node
     */
    public BinaryLinkTree(BinaryLinkNode node) {
        root = node;
    }

    public int leafNum() {
        if (root != null) {
            return root.getLeafNum();
        }

        return 0;
    }

    public void level() {
        Queue<BinaryLinkNode> queue = new Queue<>();
        queue.enQueue(root);
        while (!queue.isEmpty()) {
            BinaryLinkNode node = queue.deQueue();
            if (node.left != null) {
                queue.enQueue(node.left);
            }
            if (node.right != null) {
                queue.enQueue(node.right);
            }
            System.out.println(node.data);
        }
    }

    public void inOrder() {
        if (root != null) {
            root.inOrder();
        }
    }

    public int singleChild() {
        int result = 0;
        if (root != null) {
            return root.singleChild();
        }
        return result;
    }

    public int bothChilds() {
        int result = 0;
        if (root != null) {
            return root.bothChilds();
        }
        return result;
    }

    public int getDepth() {
        int result = 0;
        if (root != null) {
            result = root.getDepth();
        }
        return result;
    }

    public int getWidth() {
        BinaryLinkNode[] queue = new BinaryLinkNode[50];
        int front = -1;
        int rear;

        if (root != null) {
            queue[++front] = root;
            rear = front;

            while (rear - front >= 0) {
                BinaryLinkNode temp = queue[front];
                front++;
                if (temp.left != null) {
                    temp.left.layer = temp.layer + 1;
                    queue[++rear] = temp.left;
                }
                if (temp.right != null) {
                    temp.right.layer = temp.layer + 1;
                    queue[++rear] = temp.right;
                }
            }

            int count = 1;
            int max = 0;
            for (int i = 0; i < rear; i++) {
                if (queue[i].layer == queue[i + 1].layer) {
                    count++;
                    if (count > max) {
                        max = count;
                    }
                } else {
                    if (count > max) {
                        max = count;
                    }
                    count = 0;
                }
            }

            return max;
        }

        return 0;
    }

    public BinaryLinkNode search(Integer data) {
        if (root != null) {
            return root.search(data);
        }
        return null;
    }

    public static void main(String[] args) {

        BinaryLinkNode root = new BinaryLinkNode(101);
        System.out.println("root is " + root.data);

        BinaryLinkNode nodeA1 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeA2 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeB1 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeB2 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeB3 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeC1 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeC2 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeC3 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeC4 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeD1 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeD2 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeD3 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeD4 = new BinaryLinkNode(DataUtil.genNumber(100));
        BinaryLinkNode nodeD5 = new BinaryLinkNode(DataUtil.genNumber(100));

        root.left = nodeA1;
        root.right = nodeA2;
        System.out.println("level 1 is " + nodeA1.data);
        nodeA1.left = nodeB1;
        nodeA1.right = nodeB2;
        nodeA2.left = nodeB3;
        System.out.println("level 2 is " + nodeB1.data);
        nodeB2.right = nodeC2;
        nodeB1.left = nodeC1;
        nodeB3.right = nodeC3;
        nodeB3.left = nodeC4;
        System.out.println("level 3 is " + nodeC1.data);
        nodeC1.right = nodeD1;
        nodeC2.left = nodeD2;
        nodeC2.right = nodeD3;
        nodeC3.left = nodeD4;
        nodeC3.right = nodeD5;
        System.out.println("level 4 is " + nodeD1.data);

        BinaryLinkTree tree = new BinaryLinkTree(root);
        tree.level();
        tree.inOrder();


        System.out.println("Leaf Num:" + tree.leafNum());
        System.out.println("Single child Num:" + tree.singleChild());
        System.out.println("Both Childs Num:" + tree.bothChilds());
        System.out.println("Tree depth: " + tree.getDepth());
        System.out.print(nodeC2.data);
        System.out.println(" = " + tree.search(nodeC2.data).data);
        System.out.println("Width is : " + tree.getWidth());
    }
}
